/*
 * @lc app=leetcode.cn id=2332 lang=c
 *
 * [2332] 坐上公交的最晚时间
 */
// @lc code=start
static int compare(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

void print_array(int *list, int size)
{
    int i;
    for (i = 0; i < size - 1; i++)
    {
        printf("%d, ", list[i]);
    }
    printf("%d\n", list[size - 1]);
}

int latestTimeCatchTheBus(int *buses, int busesSize, int *passengers, int passengersSize, int capacity)
{

    if (!busesSize || !capacity)
    {
        return -1;
    }
    if (!passengersSize)
    {
        return buses[busesSize - 1];
    }
    // printf("busesSize:%d, passengersSize:%d, capacity:%d\n", busesSize, passengersSize, capacity);
    qsort(buses, busesSize, sizeof(*buses), compare);
    // print_array(buses, busesSize);
    qsort(passengers, passengersSize, sizeof(*passengers), compare);
    // print_array(passengers, passengersSize);
    int i, last;
    last = 0;
    int last_bus_state = 0;
    for (i = 0; i < busesSize; i++)
    {
        // printf("i:%d, last_bus_state:%d\n", i, last_bus_state);
        last_bus_state = 0;
        while (last < passengersSize && passengers[last] <= buses[i])
        {
            last_bus_state++;
            // printf("last:%d, last_bus_state:%d\n", last, last_bus_state);
            if (last_bus_state == capacity)
            {
                last++;
                break;
            }
            last++;
        }
    }
    // printf(">>> last:%d, last_bus_state:%d\n", last, last_bus_state);
    if (last == 0)
    {
        return buses[busesSize - 1];
    }
    if (last_bus_state < capacity && passengers[last - 1] < buses[busesSize - 1])
    {
        return buses[busesSize - 1];
    }
    int res_time = passengers[--last];
    // printf("res_time:%d, last:%d\n", res_time, last);
    // print_array(passengers, passengersSize);
    while (last >= 0 && res_time == passengers[last])
    {
        --res_time;
        --last;
        // printf("res_time:%d, last:%d\n", res_time, last);
    }
    // printf("return last:%d, res_time:%d\n", last, res_time);
    return res_time;
}
// @lc code=end
